statfandomcom-20200213-history
Isotonic regression
Problem Given values a_1 , ..., a_n and their positive weights w_1 , ..., w_n , approximate them by y_1 , ... y_n as close as possible, subject to a set of constraints of kind y_i \ge y_j : : Given :: values \mathbf{a} \in \Bbb{R}^n , :: weights \mathbf{w} \in \Bbb{R}^n such that w_i>0 for all i, :: set of constraints E \subset \{1,...,n\}^2 , : minimize \sum_i w_i \left( y_i-a_i \right)^2 with respect to \mathbf{y} \in \Bbb{R}^n subject to y_i \ge y_j for all (i,j)\in E If all weights equal to 1, the problem is called ''unweighted isotonic regression'', otherwise it is called ''weighted isotonic regression''. Example Minimize 3(y_1-2)^2+(y_2-1)^2+(y_3-4)^2+2y_4^2 subject to : y_1\le y_2 : y_2\le y_3 : y_2\le y_4 Linear ordering Of a particular interest is ''linear ordering isotonic regression'': : Given :: values \mathbf{a} \in \Bbb{R}^n , :: weights \mathbf{w} \in \Bbb{R}^n such that w_i>0 for all i, : minimize \sum_i w_i \left( y_i-a_i \right)^2 with respect to \mathbf{y} \in \Bbb{R}^n subject to y_1 \le y_2\le\;...\;\le y_n For linear ordering isotonic regression, there is a simple linear algorithm, called [[#Pool Adjacent Violators Algorithm|Pool Adjacent Violators Algorithm]] (PAVA). If all weights are equal 1, the problem is called ''unweighted linear ordering isotonic regression''. Example Isotonic regression for 10^6 points. * Left: points (x_i, a_i) , where a_i=0 \text{ or }1 . The probability that a_i=1 is determined by logistic function. Only 1000 points shown. * Right: outcome of isotonic regression (black graph) versus logistic function (red graph). The logistic function had been restored with high precision. Other variants Non-euclidean metrics Sometimes other metrics are used instead of the Euclidean metric, for instance L_1 metrics: : \sum_i w_i |y_i-a_i|\! or unweighted L_\infty metrics: : \max_i |y_i-a_i| Points at a grid Sometimes, each value a_i corresponds to a point x_i at 2d or higher-dimensional grid. The fit value must increase at each dimension: : y_i \le y_j \text{ if } x_{ik} \le x_{jk} \text{ for all } k Algorithms Pool Adjacent Violators Algorithm Pool Adjacent Violators Algorithm (PAVA) is a linear time (and linear memory) algorithm for [[#Linear ordering|linear ordering isotonic regression]]. The algorithm is based on the following theorem: '''Theorem''': For an optimal solution, if a_i \ge a_{i+1} , then y_i = y_{i+1} '''Proof''': suppose the opposite, i. e. y_i < y_{i+1} . Then for sufficiently small \varepsilon , we can set : y_i^\mathrm{new} = y_i + w_{i+1} \varepsilon : y_{i+1}^\mathrm{new} = y_{i+1} - w_i \varepsilon which decreases the sum \sum_i w_i(y_i-a_i)^2\! without violating the constraints. Therefore, our original solution was not optimal. Contradiction. Since y_i = y_{i+1} , we can combine both points (w_i, a_i) and (w_{i+1}, a_{i+1}) to a new point \left({w_i a_i + w_{i+1} a_{i+1} \over w_i + w_{i+1}}, w_i + w_{i+1}\right) . However, after we combine two points (w_i, a_i) and (w_{i+1},a_{i+1}) to the new point \left(w_i^\prime, a_i^\prime\right) , this new point can violate the constraint a_{i-1}\le a_i^\prime . In this case it should be combined with the (i-1)-th point. If the combined point violates its constraint, it should be combined with the previous point, etc. External links * [http://web.eecs.umich.edu/~qstout/IsoRegAlg.html Isotonic Regression Algorithms], by Quentin F. Stout - review of the best current existing algorithms R * [http://stat.ethz.ch/R-manual/R-patched/library/stats/html/isoreg.html isoreg function] (linear ordering unweighted isotonic regression) * [http://cran.r-project.org/web/packages/Iso/Iso.pdf Package "Iso"] (various functions to perform isotonic regression, not necessarily weighted or linear ordering). Comments